package newcoder_exp.justPractise;
import org.junit.*;

public class NC127 {


    public class Solution1 {
        public String LCS (String str1, String str2) {
            int len1 = str1.length(), len2 = str2.length();
            int[][] f = new int[len1 + 1][len2 + 1];
            int[][] help = new int[len1 + 1][len2 + 1];
            //f[i][0] f[0][j]默认为0
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        f[i][j] = f[i - 1][j - 1] + 1;
                        help[i][j] = 1;
                    } else {
                        if (f[i - 1][j] >= f[i][j - 1]) {
                            f[i][j] = f[i - 1][j];
                            help[i][j] = 2;
                        } else {
                            f[i][j] = f[i][j - 1];
                            help[i][j] = 3;
                        }
                    }
                }
            }
            String res = find(help, len1, len2, str1);
            return res;
        }

        private String find(int[][] help, int i, int j, String s) {
            StringBuilder sb = new StringBuilder();
            while (i > 0 && j > 0) {
                if (help[i][j] == 1) {
                    sb.insert(0, s.charAt(i - 1));
                    i--;
                    j--;
                } else if (help[i][j] == 2) {
                    i--;
                } else {
                    j--;
                }
            }
            return sb.toString();
        }
    }

    public class Solution {
        public String LCS (String str1, String str2) {
            int len1 = str1.length(), len2 = str2.length();
            int[][] f = new int[len1 + 1][len2 + 1];
            int max = 0;
            String res = "";
            //f[i][0] f[0][j]默认为0
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        f[i][j] = f[i - 1][j - 1] + 1;
                    } else {
                        f[i][j] = 0; 
                    }
                    if (f[i][j] > max) {
                        max = f[i][j];
                        res = str1.substring(i - f[i][j], i);
                    }
                }
            }
            return res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.LCS("2LQ74WK8Ld0x7d8FP8l61pD7Wsz1E9xOMp920hM948eGjL9Kb5KJt80","U08U29zzuodz16CBZ8xfpmmn5SKD80smJbK83F2T37JRqYfE76vh6hrE451uFQ100ye9hog1Y52LDk0L52SuD948eGjLz0htzd5YF9J1Y6oI7562z4T2"));
    }
}
